package leetcode.code2029;

public class Solution9 {
	boolean Alice = true;
	boolean Bob = false;

	public boolean stoneGameIX(int[] stones) {
		int[] mod = new int[3];
		for (int num : stones) {
			mod[num % 3]++;
		}
		mod[0] = (mod[0] & 1) == 1 ? 1 : 0;
		if (mod[1] > mod[2]) {
			int more = 0;
			if (mod[2] > 3) {
				more = mod[2] - 3;
				mod[2] -= more;
				mod[1] -= more;
			}
			mod[1] = Math.min(mod[1], 6);
		} else {
			int more = 0;
			if (mod[1] > 3) {
				more = mod[1] - 3;
				mod[2] -= more;
				mod[1] -= more;
			}
			mod[2] = Math.min(mod[2], 6);
		}
		Boolean[][][][] hash = new Boolean[2][mod[0] + 1][mod[1] + 1][mod[2] + 1];
		return this.stoneGameIX(Alice, hash, mod, 0);
	}

	private boolean stoneGameIX(boolean who, Boolean[][][][] hash, int[] mod, int total) {
		if (mod[0] == 0 && mod[1] == 0 && mod[2] == 0) {
			return this.Bob;
		}
		int index = who ? 0 : 1;
		if (hash[index][mod[0]][mod[1]][mod[2]] != null) {
			return hash[index][mod[0]][mod[1]][mod[2]];
		}
		for (int i = 0; i < 3; i++) {
			if (mod[i] > 0 && (total + i) % 3 != 0) {// if(有的选 && 选了还对){ 就试一试 }
				mod[i]--;
				if (this.stoneGameIX(!who, hash, mod, total + i) == who) {// 一试还是我赢了
					hash[index][mod[0]][mod[1]][mod[2]] = who;
					mod[i]++;
					return who;// 那就选这个
				}
				mod[i]++;
			}
		}
		hash[index][mod[0]][mod[1]][mod[2]] = !who;
		return !who;// 干了， 我输了
	}
}